package com.neusoft.tree;

import java.util.Objects;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 二叉排序树节点类
 * @date 2025-04-09
 */
public class BinarySortNode extends Node<Integer> {

    public BinarySortNode(Integer item) {
        super(item);
    }

    /**
     * 添加二叉排序节点
     *
     * @param node 二叉排序节点
     */
    public void add(BinarySortNode node) {
        if (Objects.isNull(node)) {
            return;
        }

        if (node.getItem() < this.getItem()) {
            if (Objects.isNull(this.getSubLeft())) {
                this.setSubLeft(node);
            } else {
                // 递归向左子树添加
                BinarySortNode subLeft = (BinarySortNode) this.getSubLeft();
                subLeft.add(node);
            }
        } else {
            if (Objects.isNull(this.getSubRight())) {
                this.setSubRight(node);
            } else {
                // 递归向右子树添加
                BinarySortNode subRight = (BinarySortNode) this.getSubRight();
                subRight.add(node);
            }
        }
    }

    /**
     * 根据值查找节点
     *
     * @param nodeValue 节点值
     * @return 查找的节点
     */
    public BinarySortNode search(int nodeValue) {
        if (nodeValue == this.getItem()) {
            // 找到就是该结点
            return this;
        } else if (nodeValue < this.getItem()) {
            // 如果查找的值小于当前结点，向左子树递归查找
            if (Objects.isNull(this.getSubLeft())) {
                // 左子结点为空
                return null;
            }
            return ((BinarySortNode) this.getSubLeft()).search(nodeValue);
        } else {
            // 如果查找的值不小于当前结点，向右子树递归查找
            if (Objects.isNull(this.getSubRight())) {
                return null;
            }
            return ((BinarySortNode) this.getSubRight()).search(nodeValue);
        }
    }

    /**
     * 查找要删除结点的父结点
     *
     * @param nodeValue 节点值
     * @return 查找的父节点
     */
    public BinarySortNode searchParentNode(int nodeValue) {
        //如果当前结点就是要删除的结点的父结点，就返回
        if ((Objects.nonNull(this.getSubLeft()) && this.getSubLeft().getItem() == nodeValue) ||
                (Objects.nonNull(this.getSubRight()) && this.getSubRight().getItem() == nodeValue)) {
            return this;
        } else {
            if (nodeValue < this.getItem() && Objects.nonNull(this.getSubLeft())) {
                //如果查找的值小于当前结点的值,并且当前结点的左子结点不为空,向左子树递归查找
                return ((BinarySortNode) this.getSubLeft()).searchParentNode(nodeValue);
            } else if (nodeValue >= this.getItem() && Objects.nonNull(this.getSubRight())) {
                // 向右子树递归查找
                return ((BinarySortNode) this.getSubRight()).searchParentNode(nodeValue);
            } else {
                // 没有找到父结点
                return null;
            }
        }
    }
}
